Skip to main content

Garbled Circuits in Interstellar

Garbled Circuits are a cryptographic primitive originally introduced by Andrew Yao, designed to enable secure two-party computation. One party (the "garbler") encrypts a circuit such that another party (the "evaluator") can compute the output without learning any of the underlying inputs or internal logic. Interstellar adapts this concept to build tamper-resistant one-time programs for secure transaction and authentication workflows.

What is a Garbled Circuit?​

A garbled circuit is a boolean logic circuit where:

  • Each gate is encoded with encrypted truth tables.
  • Inputs are replaced with cryptographic labels (random-looking tokens).
  • Only the correct combination of input labels can unlock each gate and propagate to the output.

The result is that intermediate values are never revealed, and the computation reveals only the final output—nothing more. It ensures computation privacy even if one party is potentially malicious.

Interstellar's One-Time Garbled Circuit Design​

In Interstellar, garbled circuits are deployed as One-Time Programs (OTP) to validate user operations such as:

  • Transaction approval
  • Account recovery confirmation
  • Airdrop eligibility

Each instance of the circuit is generated on demand by the blockchain and executed within the mobile app. The inputs to the garbled circuit are derived from:

  • A signature generated by the device’s Secure Element (SE)
  • Randomly sampled values tied to the current operation

These inputs are verifiably random and unique to the session. The resulting labels output by the circuit prove that the operation was conducted by a legitimate, hardware-bound device.

Why This Matters for Security​

  • Tamper-resistance: Even if a device is infected with a rootkit or malware, the garbled circuit computation is isolated. The malware cannot access or influence the secure inputs.
  • Input confidentiality: The SE signature used as a seed ensures that the attacker cannot guess or replicate valid inputs.
  • Verifiability: Blockchain nodes can verify the output labels against known one-time circuit commitments. This ensures the operation is legitimate without ever seeing the user’s secret input.

Resilience Against Adversaries​

Garbled circuits in Interstellar are designed to be secure against PPT (Probabilistic Polynomial Time) adversaries, meaning any attacker with limited computational resources—even rootkits—cannot:

  • Forge the garbled inputs without access to the SE
  • Extract useful data from circuit outputs
  • Reuse a previous circuit or replay an operation

Even if malware gains full control of the device UI, filesystem, and memory, it cannot:

  • Derive the private key or SE signature
  • Reverse-engineer or precompute valid circuit responses
  • Inject manipulated outputs that would be accepted by the blockchain

Limitations & Considerations​

While this model is highly robust, it assumes the following:

  • The Secure Element implementation itself is not compromised (e.g., no physical side-channel exploit).
  • The garbled circuit implementation in the app is correctly isolated and does not leak intermediate data via the OS.
  • Randomness sources used for circuit seeding are not observable by malware.

Mitigations include:

  • Key shares for high-value transactions may be distributed to TEEs and validated via MPC.
  • Future use of information-theoretic schemes like Nil Message Compute (NMC) to eliminate reliance on any single secure enclave.

Summary​

Interstellar uses garbled circuits as privacy-preserving one-time programs anchored in hardware-secured randomness. This creates a tamper-resistant execution layer for critical wallet actions. Even in the presence of root-level malware, the circuit’s structure, input secrecy, and blockchain-verifiable outputs make it computationally infeasible for adversaries to forge or hijack the process. Combined with MPC and TEE-side validation, this method represents a breakthrough in securing mobile-first Web3 infrastructure.